//给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。 
//
// 我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。 
//
// 
// 
//
// 必须在不使用库的sort函数的情况下解决这个问题。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [2,0,2,1,1,0]
//输出：[0,0,1,1,2,2]
// 
//
// 示例 2： 
//
// 
//输入：nums = [2,0,1]
//输出：[0,1,2]
// 
//
// 
//
// 提示： 
//
// 
// n == nums.length 
// 1 <= n <= 300 
// nums[i] 为 0、1 或 2 
// 
//
// 
//
// 进阶： 
//
// 
// 你可以不使用代码库中的排序函数来解决这道题吗？ 
// 你能想出一个仅使用常数空间的一趟扫描算法吗？ 
// 
// Related Topics 数组 双指针 排序 👍 1387 👎 0


package com.cjl.leetcode.editor.cn;

/**
 * [P75]_颜色分类
 *
 * @author cjl
 * @date 2022-09-11 22:33:06
 */
public class P75_SortColors {
    public static void main(String[] args) {
        //测试代码
        Solution solution = new P75_SortColors().new Solution();
        solution.sortColors(new int[]{2, 1, 0, 1, 1, 0});
    }

    //力扣代码
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 解题思路：
         * 1.设置3个遍历，i:0的结束位置(不包含i)；j:2的开始位置（不包含），k遍历位置
         * 2.遍历，如果是0，和i位置的元素对换，i++;
         * 3.如果是2，和j位置的元素对换，j--；
         * 4.如果是1，k++；
         *
         * @param nums
         */
        public void sortColors(int[] nums) {
            int i = 0;
            int j = nums.length - 1;
            for (int k = 0; k <= j; ) {
                if (nums[k] == 0) {
                    if (i >= k) {
                        i++;
                        k++;
                    } else {
                        int tmp = nums[i];
                        nums[i] = nums[k];
                        nums[k] = tmp;
                        i++;
                    }
                } else if (nums[k] == 2) {
                    int tmp = nums[j];
                    nums[j] = nums[k];
                    nums[k] = tmp;
                    j--;
                } else {
                    k++;
                }
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}